1. Field of the Invention
This invention relates to flash electrically-erasable programmable read-only memories (flash EEPROM) and, more particularly, to methods for releasing portions of such arrays in which data of less value is stored so that more important data may be written to such arrays in compressed form.
2. History of the Prior Art
Modern computer systems make extensive use of long term memory. Typically this memory is provided by one or more electro-mechanical hard (fixed) disk drives made of flat circular magnetic disks which rotate about a central axis and which have a mechanical arm to write to or to read from positions on the magnetic disk. Hard disk drives are very useful and have become almost a necessity to the operation of personal computers. However, such electro-mechanical drives are relatively heavy, require a significant amount of space within a computer, require a significant amount of the power in use, and are very susceptible to shock. A hard drive within a portable computer which is dropped is quite likely to cease functioning with a catastrophic loss of data.
Recently, forms of long term storage other than electro-mechanical hard disk drives have become feasible for use in computers. One of these is flash EEPROM. A flash EEPROM memory array includes a large plurality of floating-gate field effect transistors arranged as memory cells in typical row and column fashion with circuitry for accessing the individual cells and placing the memory transistors of those cells in one of two memory conditions. A flash memory cell, like a typical EPROM cell retains information when power is removed. Flash EEPROM memory has a number of attributes which adapt it to use as long term memory. It is light in weight, occupies very little space, and consumes less power than electro-mechanical disk drives. More importantly, it is especially rugged. It will withstand without adverse effects repeated drops each of which would destroy a typical electro-mechanical hard disk drive.
A peculiarity of flash EEPROM, however, is that it is erased by applying a high voltage simultaneously to the source terminals of all of the transistors (cells) used in a large portion of the array. Because these source terminals are all connected to one another in the array by metallic busing, the entire portion of the array must be erased at once. While an electro-mechanical hard disk drive will typically store information in a first area of the disk and then rewrite that same area of the disk when the information changes, this is not possible with a flash memory array without erasing all of the valid information that remains in that portion of the array along with the invalid (dirty) information.
Because of this, a different arrangement may be advantageously used for rewriting data and erasing dirty sectors of a flash EEPROM array. In a recently devised arrangement, the entire array is divided into smaller separately erasable blocks so that when a block is erased the amount of valid data which must be reprogrammed is reduced. Such an array is composed of a number of silicon chips; and each such chip includes a number of such blocks. Then, when the information at a data entry changes, the changed information is written to a new sector on an available block rather than written over the old data; and the old data is marked dirty. After a sufficient number of sectors on a block have been marked dirty, the entire block is erased. When erasure occurs, all of the valid data in the block to be erased is written to a new block; and then the dirty block is erased and put back into use as a clean block of memory. Because of this involved erasure process, it typically takes as much as two seconds to erase a block of a flash EEPROM array. However, because erasure need not occur with each entry which is rewritten, erasure may be delayed until a block contains a sufficient amount of dirty information that cleanup is feasible. This reduces the number of erasure operations to a minimum and allows erasure to occur in the background when the facilities for controlling the array are not otherwise occupied with reading and writing. Such an arrangement is described in U.S. patent application Ser. No. 969,131, entitled Method And Circuitry For A Solid State Memory Disk, S. Wells, filed Oct. 30, 1992, and assigned to the assignee of the present invention.
One embodiment of the flash EEPROM array has been designed to include a hardware compressor/decompressor so that it may store more data. A problem occurs in using such a memory array to store compressed data. The Microsoft DOS operating system (hereinafter DOS) allocates long term memory space through the use of a file allocation table associated with the particular memory hardware. When an electro-mechanical hard disk drive is first put into use, it is divided into sectors each of a fixed size and residing at a fixed place on the drive media. Each sector is numbered. The file allocation table is a way for the DOS operating system to figure out which sectors on a disk are used for a file. The file allocation table is a linked list that maps the file to the sectors; each link in the list includes a number of sectors allocated to a particular file and points to a next link. The DOS system typically saves the file allocation table on the disk with which the table is associated. The allocation of sectors in the file allocation table is the way in which the operating system determines how much memory space is available in the array. Other systems operate similarly.
However, when a flash EEPROM memory array which uses internal hardware compression is used with an operating system, an estimate of the average compression rate is used to determine an array size which is used by the operating system in establishing a file allocation table. The operating system creates a file allocation table of a particular size presuming that there are a particular number of sectors in the array. The memory array size furnished presumes that compression will occur at the average rate. If compression occurs at a lesser rate with particular data, then there will be significantly less storage space available than the operating system believes is available.
Unlike electro-mechanical hard disk drives, each block of a flash EEPROM memory array must be erased before new data may be written to it. When compressed data is being written to a flash EEPROM memory array at a lower than average compression rate so that insufficient space is available in the array for the data, there is no process for determining that this is occurring and for releasing data stored in a flash EEPROM memory array immediately so that there will be sufficient room to store the compressed data. An attempt to write a large amount of data compressed at a rate lower than average will cause the array to return a general disk write error signal. At that point, some method for releasing space in a flash memory array immediately is necessary if the new data is to be written to the array.